package com.ruoyi.wxarea;

import java.util.Arrays;


class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
public class LiKou {


    /**
     * 012. 寻找数组的中心下标
     * 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
     * 如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
     * 如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
     * @param nums {1,6,8,7,2,4,5,3,1}
     * @return
     */
    /**
     * 双滑动窗口解法
     * @param nums
     * @return
     */
    public static int pivotIndex(int[] nums) {
        int res = -1;
        int leftSum = 0;
        int rightSum = 0;
        for (int i = 0; i < nums.length; i++){
            rightSum += nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            rightSum -= nums[i];
            if (leftSum == rightSum) {
                res = i;
                break;
            }
            leftSum += nums[i];
        }
        return res;
    }
    /**
     * 88. 合并两个有序数组
     * 给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
     * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。
     * 注意：最终，合并后数组不应由函数返回而是存储在数组 nums1中。为了应对这种情况，nums1 的初始长度为 m + n，
     * 其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
     * 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
     * 输出：[1,2,2,3,5,6]
     */
    /**
     * 选择排序
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = 0;
        for (int i = m; i < nums1.length; i++) {
            nums1[i] = nums2[index++];
        }
        for (int i = 0; i < nums1.length; i++) {
            int minValue = nums1[i];
            int minIndex = i;
            for (int j = i + 1; j < nums1.length; j++) {
                if(minValue > nums1[j]){
                    minValue = nums1[j];
                    minIndex = j;
                }
            }
            if (minIndex != i){
                nums1[minIndex] = nums1[i];
                nums1[i] = minValue;
            }
        }
    }
    /**
     * 206、反转链表
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     * {1,2,3,4,5}  ---> {5,4,3,2,1}
     */
    /**
     * 迭代方法
     * @param head
     * @return
     */
    public static ListNode reverseList1(ListNode head) {
        ListNode curr = head;
        ListNode prev = null,next;
        while (curr != null){
            head = curr.next;
            curr.next = prev;
            prev = curr;
            curr = head;
        }
        return prev;
    }
    /**
     * 递归方法
     * @param head
     * @return
     */
    public static ListNode reverseList2(ListNode head) {
        if(head == null || head.next == null){
            return  head;
        }
        ListNode listNode = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return listNode;
    }

    /**
     * 643. 子数组最大平均数 I
     * 给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
     * 请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
     * 任何误差小于 10-5 的答案都将被视为正确答案。
     * 示例 1：
     * 输入：nums = [1,12,-5,-6,50,3], k = 4
     * 输出：12.75
     * 解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
     * 示例 2：
     * 输入：nums = [5], k = 1
     * 输出：5.00000
     * @param nums
     * @param k
     * @return
     */
    public static double findMaxAverage(int[] nums, int k) {
        {
            int sum = 0;
            int n = nums.length;
            for (int i = 0; i < k; i++) {
                sum += nums[i];
            }
            int maxSum = sum;
            for (int i = k; i < n; i++) {
                sum = sum - nums[
                        i - k] + nums[i];
                maxSum = Math.max(maxSum, sum);
            }
            return 1.0 * maxSum / k;

        }
    }

    public static int findCircleNum(int[][] isConnected) {
        int provinces = isConnected.length;
        boolean[] visited = new boolean[provinces];
        int circles = 0;
        for (int i = 0; i < provinces; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, provinces, i);
                circles++;
        }
    }
        return circles;
}
    public static void dfs(int[][] isConnected, boolean[] visited, int provinces, int i) {
        for (int j = 0; j < provinces; j++) {
        if (isConnected[i][j] == 1 && !visited[j]) {
            visited[j] = true;
            dfs(isConnected, visited, provinces, j);
        }
    }
}

public static void main(String[] args) {
        int[][] x = new int[][]{{1,1,0},{1,1,0},{0,0,1}};
        System.out.println(findCircleNum(x));
        /**
         * 643. 子数组最大平均数 I
         * int[] nums = {1,12,-5,-6,50,3};
         * System.out.println(findMaxAverage(nums, 3));
         */
        /** 012. 寻找数组的中心下标
         * int[] nums = {1,6,8,7,2,4,5,3,1};
         * System.out.println(pivotIndex(nums));
         */

        /**
         * 88. 合并两个有序数组
         int[] nums1 = {1,2,3,0,0,0,0};
         int m = 3, n = 3;
         int[] nums2 = {2,5,6,1};
         merge(nums1,m,nums2,n);
         */

        /**
         * 206、反转链表
         * ListNode listNode5 = new ListNode(5,null);
         *         ListNode listNode4 = new ListNode(4,listNode5);
         *         ListNode listNode3 = new ListNode(3,listNode4);
         *         ListNode listNode2 = new ListNode(2,listNode3);
         *         ListNode listNode1 = new ListNode(1,listNode2);
         *         ListNode listNode = reverseList2(listNode1);
         *         System.out.println(listNode);
         */



    }
}
